// 2015年版权所有etcd作者
// 
// 根据Apache许可证2.0版（以下简称“许可证”）获得许可；
// 除非遵守许可证，否则不得使用此文件。
// 您可以通过
// 
// www.apache.org/licenses/LICENSE-2.0 
// 
// 除非适用法律要求或书面同意，否则根据许可证分发的软件
// 按“原样”分发，
// 无任何明示或暗示的保证或条件。
// 请参阅许可证，了解管理许可的特定语言和
// 许可证下的限制。

package raft

import pb "go.etcd.io/etcd/raft/v3/raftpb"

// 存储Entry记录
// unstable使用内存数组维护其中所有的En町记录，对于Leader节点而言，它维护了客户端请求对应的En町记录；
// 对于Follower节点而言，它维护的是从Leader 节点复制来的Entry记录
// 无论是Leader节点还是Follower节点，对于刚刚接收到的En町记录首先都会被存储在unstable中
// 然后按照Raft协议将unstable中缓存的这些Entry记录交给上层模块进行处理，
// 上层模块会将这些Entry记录发送到集群其他节点或进行保存（写入Storage中）。
// 之后，上层模块会调用Advance（）方法通知底层的etcd-raft模块将unstable中对应的Entry记录删除（因为己经保存到了Storage中）。
// 正因为unstable中保存的En位y记录并未进行持久化，可能会因节点故障而意外丢失，所以被称为unstable
type unstable struct {
	// 快照数据，该快照数据也是未写入Storage中的
	snapshot *pb.Snapshot
	// ：用于保存未写入Storage中的Entry记录。
	entries []pb.Entry
	// entries中的第一条Entry记录的索引值。
	offset  uint64
	logger Logger
}

// 会尝试获取unstable的第一条Entry记录的索引值，如果获取失败则返回（Q, false）
func (u *unstable) maybeFirstIndex() (uint64, bool) {
	// 如采unstable记录了快照，则通过快照元数据返回相应的索引位
	if u.snapshot != nil {
		return u.snapshot.Metadata.Index + 1, true
	}
	return 0, false
}

// 尝试获取unstable的最后一条Entry记录的索引值,如果获取失败则返回（Q, false）
func (u *unstable) maybeLastIndex() (uint64, bool) {
	if l := len(u.entries); l != 0 {	// 检测entries切片的长度
		return u.offset + uint64(l) - 1, true	// 返回entries中最后一条Entry记录的索引值
	}
	if u.snapshot != nil {	// 如果存在快照数据，则通过其元数据返回索引位
		return u.snapshot.Metadata.Index, true
	}
	// entries和snapshot都是空的，则整个unstable其实也就没有任何数据了
	return 0, false
}

// 尝试获取指定Entry记录的Term值
func (u *unstable) maybeTerm(i uint64) (uint64, bool) {
	// 指定索引位对应的Entry记录已经不在unstable中，可能已经被持久化或是被写入快照
	if i < u.offset {
								// 检测是不是快照所包含的最后一条Entry记录
		if u.snapshot != nil && u.snapshot.Metadata.Index == i {
			return u.snapshot.Metadata.Term, true
		}
		return 0, false
	}

	// 获取unstable中最后一条Entry记录的索引
	last, ok := u.maybeLastIndex()
	if !ok {
		return 0, false
	}
	if i > last {	// 指定的索引值超出了unstable已知范围，查找失败
		return 0, false
	}
	//从entries字段中查找指定的Entry并返回其Term值
	return u.entries[i-u.offset].Term, true
}

// 当unstable.entries中的Entry记录己经被写入Storage之后，会调用unstable.stableTo（）方法清除entries中对应的Entry记录，
func (u *unstable) stableTo(i, t uint64) {
	// 查找指定Entry记录的Term值，若查找失败则表示对应的Entry不在unstable中，直接返回（
	gt, ok := u.maybeTerm(i)
	if !ok {
		return
	}

	if gt == t && i >= u.offset {	// 指定的E口try记录在unstable.entries中保存
		// 指定索引位之前的Entry记录都已经完成持久化，则将其之前的全部Entry记录删除
		u.entries = u.entries[i+1-u.offset:]
		u.offset = i + 1	// 更新offset字段
		// 随着多次追加日志和截断日志的操作，unstable.entires底层的数组会越来越大，
		// shrinkEntriesArray （）方法会在底层数组长度超过实际占用的两倍时，对底层数组进行缩减
		u.shrinkEntriesArray()
	}
}

// 随着多次追加日志和截断日志的操作，unstable.entires底层的数组会越来越大，
// shrinkEntriesArray （）方法会在底层数组长度超过实际占用的两倍时，对底层数组进行缩减
func (u *unstable) shrinkEntriesArray() {
	const lenMultiple = 2
	if len(u.entries) == 0 {	// 检测entries的长度
		u.entries = nil
	} else if len(u.entries)*lenMultiple < cap(u.entries) {
		newEntries := make([]pb.Entry, len(u.entries))	// 重新创建切片
		copy(newEntries, u.entries)	// 复制原有切片中的数据
		u.entries = newEntries	// 重置entries字段
	}
}

// 当unstable.snapshot字段指向的快照被写入Storage之后，会调用unstable.stableSnapTo()方法将snapshot字段清空
func (u *unstable) stableSnapTo(i uint64) {
	if u.snapshot != nil && u.snapshot.Metadata.Index == i {
		u.snapshot = nil
	}
}

func (u *unstable) restore(s pb.Snapshot) {
	u.offset = s.Metadata.Index + 1
	u.entries = nil
	u.snapshot = &s
}

// 向unstable.entries中追加Entry记录
func (u *unstable) truncateAndAppend(ents []pb.Entry) {
	after := ents[0].Index	// 获取第一条待追加的Entry记录的索引值
	switch {
	case after == u.offset+uint64(len(u.entries)):
		// ／若待追加的记录与e口tries中的记录正好连续，则可以直接向entries中追加
		u.entries = append(u.entries, ents...)
	case after <= u.offset:	// 直接用待追加的Entry记录替换当前的entries字段，并支新offset
		u.logger.Infof("replace the unstable entries from index %d", after)
		u.offset = after
		u.entries = ents
	default:
		// after在offset～last之间，贝rjafter～last之间的Entry记录冲突。这里会将offset~after
		// 之间的记录保留，抛弃after之后的记录，然后完成追加操作
		// unstable. slice （）方法会检测after是否合法，并返回offset’”after的切片
		u.logger.Infof("truncate the unstable entries before index %d", after)
		u.entries = append([]pb.Entry{}, u.slice(u.offset, after)...)
		u.entries = append(u.entries, ents...)
	}
}

// unstable. slice （）方法会检测after是否合法，并返回offset’”after的切片
func (u *unstable) slice(lo uint64, hi uint64) []pb.Entry {
	u.mustCheckOutOfBounds(lo, hi)
	return u.entries[lo-u.offset : hi-u.offset]
}

// u.offset<=lo<=hi<=u.offset+len（u.entries）
func (u *unstable) mustCheckOutOfBounds(lo, hi uint64) {
	if lo > hi {
		u.logger.Panicf("invalid unstable.slice %d > %d", lo, hi)
	}
	upper := u.offset + uint64(len(u.entries))
	if lo < u.offset || hi > upper {
		u.logger.Panicf("unstable.slice[%d,%d) out of bound [%d,%d]", lo, hi, u.offset, upper)
	}
}
